package vip.zhenzicheng.algorithm.leetcode.binary_search;

/**
 * <a href="https://leetcode.cn/problems/search-a-2d-matrix-ii/">搜索二维矩阵II [中等]</a>
 * <p>没有使用二分查找，使用了更优算法 O(M+N)
 *
 * @author zhenzicheng
 * @date 2022-07-18 11:28
 */
public class SearchA2dMatrixII_240 {

  public boolean searchMatrix(int[][] matrix, int target) {
    int x = matrix.length - 1;
    int y = matrix[0].length - 1;

    // 最大元素不满足直接返回
    if (matrix[x][y] < target) return false;
    // 默认从第一行，最后一列元素开始找
    int curRow = 0, curCol = y;

    while (curRow <= x && curCol >= 0) { // 边界
      if (target == matrix[curRow][curCol]) {
        return true;
      } else if (target < matrix[curRow][curCol]) {
        curCol--; // 当前列对应的更大，那这一列所有的就都大于所以往左缩一列
      } else if (target > matrix[curRow][curCol]) {
        curRow++; // 当前列较大的都小就得往下一行
      }
    }
    return false;
  }
}
